public class HashBuck <K,V>{
    static class Node {
        public int val;
        public int key;
        public Node next;

        public Node(int val, int key) {
            this.val = val;
            this.key = key;
        }
    }
        public Node[] array;
        public int usedsize;

    public HashBuck() {
        array=new Node[10];
    }

    public void put(int key,int vall){

        int index=key%array.length;
        Node cur=array[index];
        while (cur!=null){
            if(cur.key==key){
                cur.val=vall;
            }
            cur=cur.next;
        }
        //没有这个key,进行头插法
        Node node=new Node(key,vall);
        node.next=cur;
        array[index]=node;
        usedsize++;
        //超过最大容量进行扩容
        if(loadFactor()>=0.75){
            resize();

        }
    }

    private void resize() {
        //将原来的元素全部哈希到新数组
        Node[] tmparray=new Node[array.length*2];
        for (int i = 0; i <array.length ; i++) {
            Node cur=array[i];
            while (cur!=null){
                Node curNext=cur.next;
                int newIndex=cur.val%tmparray.length;
                cur.next=tmparray[newIndex];
                tmparray[newIndex]=cur;
                cur=curNext;

            }
        }
        array=tmparray;
    }

    //计算负载因子
    private double loadFactor(){
        return usedsize*1.0/array.length;
    }
    public int get(int key){
        int index=key%array.length;
        Node cur=array[index];
        while (cur!=null){
            if(cur.key==key){
                return cur.val;
            }
            cur=cur.next;
        }
        return -1;
    }

}























